package tree.structure.treetype;

import tree.structure.TreeNode;
import tree.structure.TreeUtil;


import java.util.List;

/**
 * @user 26233
 * @create 2020-04-05 17:39:05
 * @description BST
 **/

public class BinarySearchTree<T extends Comparable> {

    public TreeNode<T> getBinarySearchTree(T[] data){

        TreeNode<T> root = new TreeNode<>();
        root.setValue(data[0]);
        for(int i = 1; i < data.length; i++){
            addTreeNode(root, data[i]);
        }
        return root;
    }

    public void addTreeNode(TreeNode<T> root, T t){
        if(root == null){
            System.out.println("error");
        }
        if(root.getValue().compareTo(t) < 0){
            if(root.right == null){
                TreeNode<T> newNode = new TreeNode<>();
                newNode.setValue(t);
                root.right = newNode;
                newNode.parent = root;
            }else{
                root = root.right;
                addTreeNode(root, t);
            }
        }else{
            if(root.left == null){
                TreeNode<T> newNode = new TreeNode<>();
                newNode.setValue(t);
                root.left = newNode;
                newNode.parent = root;
            }else{
                root = root.left;
                addTreeNode(root, t);
            }
        }
    }

    // 二叉查找树查找
    public TreeNode search(TreeNode root, T t){
        while(root != null) {
            if (root.getValue().equals(t)) {
                return root;
            }
            if (t.compareTo(root.getValue()) > 0) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        return null;
    }

    // 二叉搜索树最小值
    public TreeNode minNode(TreeNode root){
        while(root.left != null){
            root = root.left;
        }
        return root;
    }

    // 查找二叉树的中序遍历的后继
    public TreeNode successor(TreeNode root, T t){
        TreeNode currentNode = search(root, t);
        if(currentNode == null)
            return null;
        if(currentNode.right != null){
            return minNode(currentNode.right);
        }
        // 后继不是父节点（当前为左节点）就是根节点（当前为右节点）
        TreeNode parent = currentNode.parent;
        while(parent != null && parent.right == currentNode){
            currentNode = currentNode.parent;
            parent = currentNode.parent;
        }
        return parent;
    }

    // 查找二叉树的中序遍历的前驱
    public TreeNode precessor(TreeNode root, T t){
        TreeNode currentNode = search(root, t);
        if(currentNode == null || currentNode == minNode(root)){
            return null;
        }
        TreeNode parent = currentNode.parent;
        if(currentNode.left == null){
            while (parent != null && parent.left == currentNode){
                currentNode = currentNode.parent;
                parent = currentNode.parent;
            }
        }else{
            return minNode(currentNode.left);
        }
        return parent;
}

    // 删除节点操作

    /**
     * @param root
     * @param t
     * @return
     *
     * 1、如果删除节点left和right都为null，则指向该节点的指针置null
     * 2、如果删除节点只有左子或右子树，则原来指向删除节点的指针指向删除节点的子树
     * 3、如果删除节点存在左右子树，则将删除节点的后继替换到删除节点
     *
     */
    public TreeNode deleteNode(TreeNode root, T t){
        TreeNode currentNode = search(root, t);
        if(currentNode == null){
            return root;
        }
        // 1、2两种情况
        if(currentNode.right == null || currentNode.left == null){
            if (currentNode.parent.left == currentNode){
                if(currentNode.left == null){
                    currentNode.parent.left = currentNode.right;
                }else{
                    currentNode.parent.left = currentNode.left;
                }
            }else{
                if(currentNode.left == null){
                    currentNode.parent.right = currentNode.right;
                }else{
                    currentNode.parent.right = currentNode.left;
                }
            }
        }
        // 第3种情况
        if(currentNode.left != null && currentNode.right != null){
            TreeNode successor = successor(root, t);
            if(successor.parent.left == successor){
                successor.parent.left = successor.right;// 后继至多只有一个子女
            }else{
                successor.parent.right = successor.right;// 不在左节点上
            }
            currentNode.setValue(successor.getValue());
        }
        return root;
    }

    public static void main(String[] args){

        Integer[] data = new Integer[]{7, 1, 4, 5, 9, 3, 2, 20, 15, 16, 21, 8};
        TreeNode<Integer> root = new BinarySearchTree<Integer>().getBinarySearchTree(data);

        // 二叉搜索树中序遍历输出有序数据
        List<Integer> inOrder = new TreeUtil<Integer>().midOrder(root);

        TreeNode result = new BinarySearchTree<Integer>().search(root, 7);

        TreeNode successor = new BinarySearchTree<Integer>().successor(root, 3);
        TreeNode preccessor = new BinarySearchTree<Integer>().precessor(root, 9);

        TreeNode delete = new BinarySearchTree<Integer>().deleteNode(root, 9);

        System.out.println("end");
    }

}
